// 给定一个二叉树，返回它的中序遍历。

// 暴露方法
function inorderTraversal(root: TreeNode | null): number[] {
    const res: number[] = [];// 结果数组
    inorderTraversal_DFS(root, res);
    return res;
};

// 深度优先遍历辅助方法
function inorderTraversal_DFS(root: TreeNode | null, res: number[]) {
    if(root == null){// 递归出口
        return;
    }
    // 按照左中右的顺序遍历
    inorderTraversal_DFS(root.left,res);
    res.push(root.val);
    inorderTraversal_DFS(root.right,res);
}


// 这道题的难度非常小了，实现一个中序遍历我们常用的操作是基于系统栈来实现
// 而系统栈实际上就是利用了递归函数的方法
// 只要搞清楚中序遍历的递归出口，以及左中右的深度优先遍历顺序这道题就没什么难度
// 此外还可以考虑基于普通栈的非递归实现。